Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

\[ \newcommand{\IR}{\mathbb{R}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRp}{\IR_{\gt 0}} \newcommand{\IN}{\mathbb{N}} \newcommand{\INo}{\IN_0} \newcommand{\INs}{\IN^\ast} \newcommand{\coloneqq}{\mathbin{:=}} \newcommand{\eqqcolon}{\mathbin{=:}} \newcommand{\coloniff}{\mathbin{:\!\!\iff}} \newcommand{\dcup}{\mathbin{\dot\cup}} \newcommand{\sMid}{\,|\,} \newcommand{\Set}[1]{\left\lbrace#1\right\rbrace} \newcommand{\SMid}{\,\middle|\,} \newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\Abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[1]{\lVert#1\rVert} \newcommand{\Norm}[1]{\left\lVert#1\right\rVert} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\transp}{^\top} \newcommand{\sgn}{\mathop{\mathrm{sgn}}} \newcommand{\eps}{\varepsilon} \newcommand{\rddots}{\large{\small.}^{.^.}} \newcommand{\CharF}[1]{\chi_{#1}} \newcommand{\classFP}{\mathrm{FP}} \newcommand{\classFNP}{\mathrm{FNP}} \newcommand{\classFNPC}{\mathrm{FNPC}} \newcommand{\classTFNP}{\mathrm{TFNP}} \newcommand{\classPPAD}{\mathrm{PPAD}} \newcommand{\classPLS}{\mathrm{PLS}} \newcommand{\SocOptPNEinUnwCong}{\style{font-variant-caps:small-caps}{\text{SocOptPNEinUnwCong}\hspace{1em}}} \newcommand{\HamiltonCycle}{\style{font-variant-caps:small-caps}{\text{HamiltonCycle}\hspace{1em}}} \newcommand{\LocalMaxCut}{\style{font-variant-caps:small-caps}{\text{LocalMaxCut with Flip-Neighbourhood}\,}} \newcommand{\plInitk}{{\color{var(--plInitkCol)}\mathrm{Init}^k}} \newcommand{\plTriggerk}{{\color{var(--plTriggerkCol)}\mathrm{Trigger}^k}} \newcommand{\plTriggerkp}{{\color{var(--plTriggerkpCol)}\mathrm{Trigger}^{k+1}}} \newcommand{\plPlayerAk}{{\color{var(--plPlayerAkCol)}\mathrm{Player}_1^k}} \newcommand{\plPlayerBk}{{\color{var(--plPlayerBkCol)}\mathrm{Player}_2^k}} \newcommand{\plStart}{{\color{var(--plStartCol)}\mathrm{Start}}} \]

§4 Congestion Games

  • finite set of players $N$
  • finite set of resources $R$
  • sets of strategies $S_i \subseteq \IR^R$
  • $\ell: S \to \IR^R, s \mapsto \ell(s) \coloneqq \sum_{i \in N}s_i$ load/congestion vector
  • player specific, load-dependent, per-unit resource costs $c_i: \IR^R \to \IR^R$
  • players' cost functions $\pi_i: S \to \IR, s \mapsto s_i\transp c_i(\ell(s)) = \sum_{r \in R}s_{i,r}c_{i,r}(\ell(s))$
⤳ generic congestion game $(N,S,\pi)$   (cost minimization game!)
N = \{ \color{var(--pl1col)}1 \color{var(--pl2col)}2 \} \color{var(--pl1col)}S_1 = \{\hspace{1.2cm},\hspace{1.2cm}\class{tempstep}{\data{tempstep-classes=13-100:inactive}{\}}} \color{var(--pl2col)}S_2 = \{\hspace{1.2cm},\hspace{1.2cm}\} \color{gray}r_1 \color{gray}r_2 \color{gray}r_3 \color{gray}r_4 \color{black}\ell_{r_2} \small\color{black}c_{r_2,\color{var(--pl1col)}1}(\ell(s)) \color{black}\cdot
  • unweighted congestion game
$\coloniff S_i \subseteq \set{0,1}^R$
  • weighted congestion game
$\coloniff S_i \subseteq \set{0,d_i}^R$
  • player-independent/homogeneous costs
$\coloniff \forall i,j \in N: c_i = c_j$
  • separable costs
$\coloniff \ell_r(s) = \ell_r(s') \implies c_{i,r}(\ell(s)) = c_{i,r}(\ell(s'))$

§4.2 Unweighted Congestion Games

§4.3 Weighted Congestion Games

Here: Only weighted congestion games (with separable, homog. cost functions)
⤳ each player has a weight $d_i \in \IRnn$
⤳ set of resources used by player $i$ (under $s_i$) $R(s_i) \coloneqq \set{r \in R \sMid s_{i,r} = d_i}$
⤳ $\pi_i(s) = \sum_{r \in R(s_i)}d_i\cdot c_r\Big(\sum_{\substack{j \in N:\\ r \in R(s_j)}}d_j\Big)$
all finite games weighted pot. exactpot. games weightedcong. games unweightedcong. games \large\cong \large\cong
Thm. 4.40: Every finite game is isomorphic to a weighted congestion game.
games $G=(N,S,u)$, $H=(N,T,v)$ isomorphic if $\exists \phi_i: S_i \to T_i$ bijections s.th. $\forall i \in N, s \in S: u_i(s) = v_i(\phi_1(s_1), \dots, \phi_n(s_n))$
game $G=(N,S,u)$ $\mapsto$ weighted cong. game $H=(N,T,\pi)$:
  • $R \coloneqq S$
  • $R(T_i) \coloneqq \Set{\bigcup_{s_{-i} \in S_i}\set{(s_i,s_{-i})} \SMid s_i \in S_i}$
  • weights $d_i \coloneqq n+i-2$, where $n \coloneqq \abs{N}$
  • $c_s(l) \coloneqq \begin{cases}\class{tempstep a}{\data{tempstep-list=8-35;61-100}{\sum_{s_{-i}'}\Bigl(\prod_{j \neq i}\bigl(\frac{1}{k-1}-\CharF{s_j'=s_j}\bigr)\Bigr)\cdot\frac{u_i(s_i,s'_{-i})}{d_i}}}, &\text{if } l = d_i\\0, &\text{else}\end{cases}$

Obs: $d_i+d_j \geq 2n-1 \gt d_k$ f.a. $i,j,k \in N$.

\begin{align*} \pi_i(\phi(s)) &\phantom{=d_i\cdot\sum_{\substack{\bar s \in S:\, \bar s_i = s_i,\\\bar s_j \neq s_j \text{ f.a. } j \neq i}}\sum_{s'_{-i} \in S_{-i}}\Bigl(\prod_{j \neq i}\bigl(\tfrac{1}{k-1}-\chi_{s'_j=\bar s_j}\bigr)\Bigr)\tfrac{u_i(s_i,s'_{-i})}{d_i}} \end{align*}
\begin{align*} \phantom{\pi_i(\phi(s))} &=d_i\cdot\sum_{\substack{\bar s \in S:\, \bar s_i = s_i,\\\bar s_j \neq s_j \text{ f.a. } j \neq i}}c_{r(\bar s)}(d_i)\phantom{\Big)} \\ &\phantom{=d_i\cdot\sum_{\substack{\bar s \in S:\, \bar s_i = s_i,\\\bar s_j \neq s_j \text{ f.a. } j \neq i}}\sum_{s'_{-i} \in S_{-i}}\Bigl(\prod_{j \neq i}\bigl(\tfrac{1}{k-1}-\chi_{s'_j=\bar s_j}\bigr)\Bigr)\tfrac{u_i(s_i,s'_{-i})}{d_i}} \end{align*}
\begin{align*} \phantom{\pi_i(\phi(s))} &=d_i\cdot\sum_{\substack{\bar s \in S:\, \bar s_i = s_i,\\\bar s_j \neq s_j \text{ f.a. } j \neq i}}\sum_{s'_{-i} \in S_{-i}}\Bigl(\prod_{j \neq i}\bigl(\tfrac{1}{k-1}-\chi_{s'_j=\bar s_j}\bigr)\Bigr)\tfrac{u_i(s_i,s'_{-i})}{d_i} \end{align*}
\begin{align*} \phantom{\pi_i(\phi(s))} &=d_i\cdot\sum_{s'_{-i} \in S_{-i}}\sum_{\substack{\bar s \in S:\, \bar s_i = s_i,\\\bar s_j \neq s_j \text{ f.a. } j \neq i}}\Bigl(\prod_{j \neq i}\bigl(\tfrac{1}{k-1}-\chi_{s'_j=\bar s_j}\bigr)\Bigr)\tfrac{u_i(s_i,s'_{-i})}{d_i} \end{align*}
\begin{align*} \phantom{\pi_i(\phi(s))} &=\sum_{s'_{-i} \in S_{-i}}u_i(s_i,s'_{-i})\cdot \sum_{\substack{\bar s \in S:\, \bar s_i = s_i,\\\bar s_j \neq s_j \text{ f.a. } j \neq i}}\prod_{j \neq i}\bigl(\tfrac{1}{k-1}-\chi_{s'_j=\bar s_j}\bigr)\phantom{\Big)}\\ &\phantom{=d_i\cdot\sum_{s'_{-i} \in S_{-i}}\sum_{\substack{\bar s \in S:\, \bar s_i = s_i,\\\bar s_j \neq s_j \text{ f.a. } j \neq i}}\Bigl(\prod_{j \neq i}\bigl(\tfrac{1}{k-1}-\chi_{s'_j=\bar s_j}\bigr)\Bigr)\tfrac{u_i(s_i,s'_{-i})}{d_i}} \end{align*}
\begin{align*} \phantom{\pi_i(\phi(s))} &=\sum_{s'_{-i} \in S_{-i}}u_i(s_i,s'_{-i})\cdot \prod_{j \neq i}\sum_{\substack{\bar s_j \in S_j:\\\bar s_j \neq s_j}}\bigl(\tfrac{1}{k-1}-\chi_{s'_j=\bar s_j}\bigr)\phantom{\Big)}\\ &\phantom{=d_i\cdot\sum_{s'_{-i} \in S_{-i}}\sum_{\substack{\bar s \in S:\, \bar s_i = s_i,\\\bar s_j \neq s_j \text{ f.a. } j \neq i}}\Bigl(\prod_{j \neq i}\bigl(\tfrac{1}{k-1}-\chi_{s'_j=\bar s_j}\bigr)\Bigr)\tfrac{u_i(s_i,s'_{-i})}{d_i}} \end{align*}
\begin{align*} \phantom{\pi_i(\phi(s))} &=\sum_{s'_{-i} \in S_{-i}}u_i(s_i,s'_{-i})\cdot \prod_{j \neq i}\bigl(\tfrac{\abs{S_j \setminus \{s_j\}}}{k-1}-\chi_{s'_j \neq s_j}\bigr)\phantom{\Big)}\\ &\phantom{=d_i\cdot\sum_{s'_{-i} \in S_{-i}}\sum_{\substack{\bar s \in S:\, \bar s_i = s_i,\\\bar s_j \neq s_j \text{ f.a. } j \neq i}}\Bigl(\prod_{j \neq i}\bigl(\tfrac{1}{k-1}-\chi_{s'_j=\bar s_j}\bigr)\Bigr)\tfrac{u_i(s_i,s'_{-i})}{d_i}} \end{align*}
\begin{align*} \phantom{\pi_i(\phi(s))} &=\sum_{s'_{-i} \in S_{-i}}u_i(s_i,s'_{-i})\cdot \prod_{j \neq i}\bigl(1-\chi_{s'_j \neq s_j}\bigr)\phantom{\Big)}\\ &\class{tempstep a}{\data{tempstep-from=34}{\,=\sum_{s'_{-i} \in S_{-i}}u_i(s_i,s'_{-i})\cdot \chi_{s'_{-i}=s_{-i}}}} \\ &\class{tempstep a}{\data{tempstep-from=35}{\,= u_i(s_i,s_{-i}) = u_i(s).}}\phantom{\Big)}\\ &\phantom{=d_i\cdot\sum_{s'_{-i} \in S_{-i}}\sum_{\substack{\bar s \in S:\, \bar s_i = s_i,\\\bar s_j \neq s_j \text{ f.a. } j \neq i}}\Bigl(\prod_{j \neq i}\bigl(\tfrac{1}{k-1}-\chi_{s'_j=\bar s_j}\bigr)\Bigr)\tfrac{u_i(s_i,s'_{-i})}{d_i}} \end{align*}
$\rddots$$\cdots$${\color{var(--blue)}s_2}$$\cdots$
$\vdots$
${\color{var(--red)}s_1}$$\phantom{({\color{var(--red)}s_1},{\color{var(--blue)}s_2},{\color{var(--green)}s_3})}$
$\vdots$
$\cdots$${\color{var(--blue)}s_2}$$\cdots$
$\vdots$
${\color{var(--red)}s_1}$$\phantom{({\color{var(--red)}s_1},{\color{var(--blue)}s_2},{\color{var(--green)}s_3})}$
$\vdots$
$\cdots$${\color{var(--blue)}s_2}$$\cdots$
$\vdots$
${\color{var(--red)}s_1}$$({\color{var(--red)}s_1},{\color{var(--blue)}s_2})\phantom{,{\color{var(--green)}s_3}}$
$\vdots$
${\color{var(--green)}s_3}$$\cdots$${\color{var(--blue)}s_2}$$\cdots$
$\vdots$
${\color{var(--red)}s_1}$$({\color{var(--red)}s_1},{\color{var(--blue)}s_2},{\color{var(--green)}s_3})$
$\vdots$
$\rddots$$\cdots$${\color{var(--blue)}s_2}$$\cdots$
$\vdots$
${\color{var(--red)}s_1}$$\phantom{({\color{var(--red)}s_1},{\color{var(--blue)}s_2},{\color{var(--green)}s_3})}$
$\vdots$
\rddots \cdots \vdots s \cdots \vdots \rddots
Thm. 4.41: Weighted cong. games with affine res. costs have PNE.
Thm. 4.41:mmmm i.e. $c_r(z) = a_r\cdot z+b_r$
exact potential:
\[\require{mathtools}P: S \to \IR, s \mapsto \sum_{r \in R}\sum_{i \in N:\; r \in R(s_i)}d_i \cdot c_r\bigl(\sum_{\mathclap{j \leq i:\; r \in R(s_j)}}d_j\bigr)\]
Thm. 4.42: W. cong. games with exponential res. costs have PNE.
Thm. 4.42:mmmm i.e. $c_r(z) = a_r e^{\phi z}+b_r$ with $\phi \in \IR$ fixed!
weighted potential:
\[P: S \to \IR, s \mapsto \sum_{r \in R}\sum_{i \in N:\; r \in R(s_i)}\!\!\!\!\!\!\!\!\sgn(\phi)(1-e^{-\phi d_i})\cdot c_r\bigl(\sum_{\mathclap{j \leq i:\; r \in R(s_j)}}d_j\bigr)\]
Thm. 4.5: Every unweighted congestion game has a PNE.
  Rosenthal potential: $P: S \to \IR, s \mapsto \sum_{r \in R}\sum_{k=1}^{\ell_r(s)}c_r(k)$
Computational Game Theory (WiSe25/26), §4.3 Weighted Congestion Games
Lukas Graf (lukas.graf@uni-passau.de)
↑ All Slides